home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / cug106 / queue.c < prev    next >
Text File  |  1984-06-14  |  15KB  |  588 lines
  1. /* FIFO queue package 
  2.  (W) Copywrong 1980 Scott W. Layson
  3.  
  4. These cute little routines implement First In, First Out queues.  There
  5. are complete sets of routines provided: one to handle integer-sized
  6. (2-byte) objects, and the other to handle byte-sized things.
  7.  
  8. The routines are good for applications such as I/O buffering in programs
  9. that do several things at once.  For example, consider the following
  10. program fragment (remember that all this text is one big comment!):
  11.  
  12. #define KBD_Q_SIZE 40
  13.  
  14. struct cqueue {
  15.     char *cruft[4], space[KBD_Q_SIZE];
  16.     } kbd_q;
  17.  
  18. / * This program eats command characters and does something hairy with them * /
  19.  
  20. main()
  21. {
  22.     <... assorted declarations ...>
  23.     CQInit (&kbd_q, KBD_Q_SIZE);
  24.     while (1) do
  25.       {    cmd = get_qd_char();
  26.         hairily_process (cmd);
  27.       }
  28. }
  29.  
  30. / * Return a character off the queue if there are any, otherwise wait
  31.    for one to be typed * /
  32.  
  33. get_qd_char()
  34. {
  35.     if (!CQEmpty(&kbd_q)
  36.         return CQGrab(&kbd_q);
  37.         else return getchar();
  38. }
  39.  
  40. / * If a character has been typed, queue it * /
  41.  
  42. kbd_check()
  43. {
  44.     if (kbhit())
  45.         CQShove (getchar(), &kbd_q);
  46. }
  47.     
  48.  
  49. Careful scattering of calls to kbd_check throughout hairily_process()
  50. will prevent keyboard characters from being missed no matter how far
  51. the user types ahead (up to the KBD_Q_SIZE, of course).
  52.  
  53. Small misfeature: the queue will actually hold one fewer object than
  54. the size allocated for it.  E.g., the above kbd_q will hold
  55. (KBD_Q_SIZE - 1) characters.  This usually doesn't matter, as usual
  56. practice is just to make a queue much larger than it really has to be
  57. anyway.
  58.  
  59. ************** End of comments **********************************/
  60.  
  61.  
  62. struct queue {
  63.     int *head, *tail, *top, *bottom, space;
  64.  };
  65.  
  66.  
  67. /*  Initialization routine (must be called before any operation is done
  68.     on the queue) */
  69.  
  70. QInit(queue_p,size)
  71. struct queue *queue_p;
  72. int size;
  73. {
  74.     queue_p->head = queue_p->tail = queue_p->top = &(queue_p->space);
  75.     queue_p->bottom = queue_p->top +size -1;
  76. }
  77.  
  78.  
  79. /* Routine to grab something off the head of a queue
  80.    Does no error checking!  Be careful of underflow! */
  81.  
  82. QGrab(queue_p)
  83. struct queue *queue_p;
  84. {
  85.     return ((queue_p->head >= queue_p->bottom) ?
  86.         *(queue_p->head = queue_p->top) :
  87.          *++(queue_p->head));
  88. }
  89.  
  90.  
  91. /* Routine to shove something onto the tail of a queue
  92.    Does no error checking! BE careful of underflow! */
  93.  
  94. QShove(x,queue_p)
  95. struct queue *queue_p;
  96. int x;
  97. {
  98.     *((queue_p->tail >= queue_p->bottom) ?
  99.          (queue_p->tail = queue_p->top) :
  100.          ++(queue_p->tail)) = x;
  101. }
  102.  
  103.  
  104. /* Emptiness predicate */
  105.  
  106. QEmpty(queue_p)
  107. struct queue *queue_p;
  108. {
  109.     return (queue_p->head == queue_p->tail);
  110. }
  111.  
  112.  
  113. /* Fullness predicate */
  114.  
  115. QFull(queue_p)
  116. struct queue *queue_p;
  117. {
  118.     return((queue_p->tail+1 == queue_p->head) ||
  119.         (queue_p->tail == queue_p->bottom &&
  120.          queue_p->head == queue_p->top));
  121. }
  122.  
  123.  
  124. /* Peek at head of queue without disturbing it */
  125.  
  126. QPeek(queue_p)
  127. struct queue *queue_p;
  128. {
  129.     return (  (queue_p->head == queue_p->bottom) ?
  130.             *queue_p->top :
  131.             *(queue_p->head + 1) );
  132. }
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139. /* Here is the same repertoire of routines, but set up for
  140.    characters instead of integers:
  141. */
  142.  
  143.  
  144. struct cqueue {
  145.     char *chead, *ctail, *ctop, *cbottom, cspace;
  146.  };
  147.  
  148.  
  149. /*  Initialization routine (must be called before any operation done
  150.     on the queue) */
  151.  
  152. CQInit(queue_p,size)
  153. struct cqueue *queue_p;
  154. int size;
  155. {
  156.     queue_p->chead = queue_p->ctail = queue_p->ctop = &(queue_p->cspace);
  157.     queue_p->cbottom = queue_p->ctop +size -1;
  158. }
  159.  
  160.  
  161. /* Routine to grab something off the head of a queue
  162. Does no error checking!  Be careful of underflow! */
  163.  
  164. CQGrab(queue_p)
  165. struct cqueue *queue_p;
  166. {
  167.     return ((queue_p->chead >= queue_p->cbottom) ?
  168.         *(queue_p->chead = queue_p->ctop) :
  169.          *++(queue_p->chead));
  170. }
  171.  
  172.  
  173. /* Routine to shove something onto the tail of a queue
  174.    Does no error checking!  Be careful of overflow! */
  175.  
  176. CQShove(x,queue_p)
  177. struct cqueue *queue_p;
  178. int x;
  179. {
  180.     *((queue_p->ctail >= queue_p->cbottom) ?
  181.          (queue_p->ctail = queue_p->ctop) :
  182.          ++(queue_p->ctail)) = x;
  183. }
  184.  
  185.  
  186. /* Emptiness predicate */
  187.  
  188. CQEmpty(queue_p)
  189. struct cqueue *queue_p;
  190. {
  191.     return (queue_p->chead == queue_p->ctail);
  192. }
  193.  
  194.  
  195. /* Fullness predicate */
  196.  
  197. CQFull(queue_p)
  198. struct cqueue *queue_p;
  199. {
  200.     return((queue_p->ctail+1 == queue_p->chead) ||
  201.         (queue_p->ctail == queue_p->cbottom &&
  202.          queue_p->chead == queue_p->ctop));
  203. }
  204.  
  205.  
  206. /* Peek at head of queue without disturbing it */
  207.  
  208. CQPeek(queue_p)
  209. struct cqueue *queue_p;
  210. {
  211.     return ( (queue_p->chead == queue_p->cbottom)  ?
  212.            *queue_p->ctop  :
  213.            queue_p->chead[1] );
  214. }
  215.  
  216.     w`i~#foσ!    ~#fo"∙Eß"≈E┼!    DM═┴!    n&"≈E┼!    DM═┴╔CXENTERGR┴PLO╘EXITGRA╨~├ ├├├*≈Eδ`is#r*∙Eδ!    s#r:√E!    w:²E!    w!    n&"≈E┼!    DM═┴`i~#foσ!    ~#foσ!    n&"√Eß"∙Eß"≈E┼!    DM═┴┼!    DM═    ┴╔BozPUTCHA╥├├!"≈E┼═┴!M"≈E┼═┴╔PUTCHA╥├├!"≈E┼═┴!8"≈E┼═┴╔PUTCHA╥├├!"≈E┼═┴!7"≈E┼═┴╔PUTCHA╥EXTDI╟î├    /*    ---------------------------------------------------------
  217.     Mods by H Moran:
  218.  
  219.     In case you wish to adopt some but not all of the mods:
  220.     Lines modified by HRM marked with comment 'HRM mod'
  221.     Lines added by HRM marked with comment 'HRM'
  222.  
  223.  
  224.     1) added functions: for list reader and punch devices
  225.  
  226.         lprintf pprintf        -- list and punch devices
  227.         rscanf            -- reader device
  228.         rgets            -- reader device
  229.         lputs   pputs        -- list and punch devices
  230.         lputc   pputc        -- list and punch devices
  231.         rgetc            -- reader device
  232.  
  233.     2) sprintf() modified to use '0' for left fill char
  234.        when radix is not decimal.
  235.  
  236.     3) binary field spec added to sprintf() and sscanf()
  237.        spec used is %b
  238.  
  239.     4) pad char for non-decimal numeric fields in sprintf()
  240.        changed to '0'
  241.  
  242.     5) printing of a..f changed to A..F in _uspr()
  243.  
  244.     6) fgets() fixed to remember reception of 0x1a
  245.        and handle it as EOF. See the one caveat in
  246.        the modified comments.
  247.     -------------------------------------------------------
  248. */
  249.  
  250. /*
  251.     This file contains the source for the following
  252.     library functions:
  253.  
  254.     printf **    fprintf    **    sprintf *
  255.     scanf        fscanf        sscanf
  256.     gets        fgets
  257.     puts        fputs
  258.     swapin ***
  259.  
  260.     *) rewritten for 1.31
  261.     **) work differently since they use the new "sprintf"
  262.     ***) brand new for 1.31
  263.  
  264.     An alternate version of "sprintf" is given in the file
  265.     FLOAT.C for use with floating point numbers; see FLOAT.C
  266.     for details. Note that "sprintf" is used by "printf", so
  267.     this really amounts to an alternate version of "printf",
  268.     too.
  269.  
  270.     Note that all the upper-level formatted I/O functions
  271.     ("printf", "fprintf", "scanf", and "fscanf") now use
  272.     "sprintf" and "sscanf" for doing conversions. While
  273.     this leads to very structured source code, it also
  274.     means that calls to "scanf" and "fscanf" must process
  275.     ALL the information on a line of text; if the format
  276.     string runs out and there is still text left in the
  277.     line being processed, the text will be lost (i.e., the
  278.     NEXT scanf or fscanf call will NOT find it.)
  279.  
  280.     Also note that temporary work space is declared within
  281.     each of the high-level functions as a one-dimensional
  282.     character array. The length limit on this array is
  283.     presently set to 132 by the #define MAXLINE statement;
  284.     if you intend to create longer lines through printf,
  285.     fprintf, scanf, or fscanf calls, be SURE to raise this
  286.     limit by changing the #define statement.
  287.  
  288.     Some misc. comments on hacking text files with CP/M:
  289.     The conventional CP/M text format calls for each
  290.     line to be terminated by a CR-LF combination. In the
  291.     world of C programming, though, we like to just use
  292.     a single LF (also called a newline) to terminate
  293.     lines. AND SO, the functions which deal with reading
  294.     and writing text from disk files to memory and vice-
  295.     versa ("fgets", "fputs") take special pains to convert
  296.     CR-LF combinations into single '\n' characters when
  297.     reading from disk ("fgets"), and convert '\n' char-
  298.     acters to CR-LF combinations when writing TO disk
  299.     ("fputs"). This allows the C programmer to do things
  300.     in style, dealing only with a single line terminator,
  301.     while maintaining compatibility with the CP/M text
  302.     format (so that, for example, a text file can be
  303.     "type"d under the CCP.)
  304.     To confuse matters further, the "gets" function
  305.     (which simply buffers up a line of console input)
  306.     terminates a line with '\0' (a zero byte) instead
  307.     of CR or LF. Thus, if you wanted to read in lines
  308.     of input from the console and write them to a file,
  309.     you'd have to manually put out the CR and LF at the
  310.     end of every line. Oh, and don't forget the 0x1a
  311.     (control-Z) at the end of the file! Hey, kiddies,
  312.     isn't CP/M fun to work with???
  313.     Also, watch out when reading in text files using
  314.     "getc". While a text file is USUALLY terminated
  315.     with a control-Z, it MAY NOT BE if the file ends
  316.     on an even sector boundary. This means that there
  317.     are two possible return values from "getc" which
  318.     signal and EOF: 0x1a (control-Z), and -1 (or 255
  319.     if you assign it to a char variable.)
  320. */
  321.  
  322.  
  323. #define RAM 0        /* start of CP/M RAM area */
  324. #define MAXLINE 132    /* maximum length of text line */
  325. #define EOF -1        /* End of file val returned by getc */
  326. #define NULL 0        /* Returned by fgets on EOF */
  327.  
  328. char toupper(), isdigit();
  329.  
  330. struct buf {
  331.     int fd;
  332.     int nleft;
  333.     char *nextp;
  334.     char buff[128];
  335.  };
  336.  
  337. /*
  338.     printf
  339.  
  340.     usage:
  341.         printf(format, arg1, arg2, ...);
  342.     
  343.     Note that since the sprintf function is used to
  344.     form the output string and then puts is used to
  345.     actually print it out, care must be taken to 
  346.     avoid generating null (zero) bytes in the output,
  347.     since such a byte will terminate printing of the
  348.     string by puts. Thus, a statment such as:
  349.         printf("%c foo",'\0');
  350.     would print nothing at all.
  351.     See the "sprintf" documentation, below, for more info.
  352. */
  353.  
  354. printf(format)
  355. char *format;
  356. {
  357.     char line[MAXLINE];
  358.     _mvl();
  359.     sprintf(line,format);
  360.     puts(line);
  361. }
  362.  
  363.  
  364. /*
  365.     fprintf:
  366.     Like printf, except that the first argument is
  367.     a pointer to a buffered I/O buffer, and the text
  368.     is written to the file described by the buffer:
  369.     (-1 returned on error)
  370.     usage:
  371.         fprintf(iobuf, format, arg1, arg2, ...);
  372. */
  373.  
  374. fprintf(iobuf,format)
  375. char *format;
  376. struct buf *iobuf;
  377. {
  378.     char text[MAXLINE];
  379.     sprintf(text);
  380.     return fputs(text,iobuf);
  381. }
  382.  
  383.  
  384. /*
  385.     fscanf:
  386.     Like scanf, except that the first argument is
  387.     a pointer to a buffered input file buffer, and
  388.     the text is taken from the file instead of from
  389.     the console.
  390.     Usage:
  391.         fscanf(iobuf, format, ptr1, ptr2, ...);
  392.     Returns number of items matched (zero on EOF.)
  393.     Note that any unprocessed text is lost forever. Each
  394.     time scanf is called, a new line of input is gotten
  395.     from the file, and any information left over from
  396.     the last call is wiped out. Thus, the text in the
  397.     file must be arranged such that a single call to
  398.     fscanf will always get all the required data on a
  399.     line.
  400. */
  401.  
  402. int fscanf(iobuf,format,arg1)
  403. char *format;
  404. struct buf *iobuf;
  405. {
  406.     char text[MAXLINE];
  407.     if (!fgets(text,iobuf)) return 0;
  408.     return sscanf(text,format,arg1);
  409. }
  410.  
  411.  
  412. /*
  413.     scanf:
  414.     This one accepts a line of input text from the
  415.     console, and converts the text to the required
  416.     binary or alphanumeric form (see Kernighan &
  417.     Ritchie for a more thorough description):
  418.     Usage:
  419.         scanf(format, ptr1, ptr2, ...);
  420.     Returns number of items matched.
  421.     Since a new line of text must be entered from the
  422.     console each time scanf is called, any unprocessed
  423.     text left over from the last call is lost forever.
  424.     This is a difference between BDS scanf and UNIX
  425.     scanf. Another is that the field width specification
  426.     is not supported here.
  427. */
  428.  
  429. scanf(format)
  430. char *format;
  431. {
  432.     char line[MAXLINE];
  433.     _mvl();
  434.     gets(line);
  435.     sscanf(line,format);
  436. }
  437.  
  438.  
  439. /*
  440.     Internal function to move all function arguments
  441.     over one place to the right, to make room for
  442.     a new argument in the first position. This is
  443.     necessary so that, for example, "sprintf" can
  444.     be called from within "printf" without clobbering
  445.     one of the arguments. This is NOT a portable
  446.     feature of BDS C, and in fact represents one of
  447.     the biggest kludges in the package. Oh well; live
  448.     and learn.
  449. */
  450.  
  451. _mvl()
  452. {
  453.     int count, *ptr;
  454.     ptr = (RAM + 0x3f7 + 0x2e);
  455.     count = 23;
  456.     while (count--) *ptr = *--ptr;
  457. }
  458.  
  459.  
  460. /*
  461.     sprintf:
  462.     Like fprintf, except a string pointer is specified
  463.     instead of a buffer pointer. The text is written
  464.     to where the string pointer points.
  465.     Usage:
  466.         sprintf(string,format,arg1, arg2, ...);
  467.  
  468.     This is my latest version of the "sprintf" standard library
  469.     routine. This time, folks, it REALLY IS standard. I've
  470.     tried to make it EXACTLY the same as the version presented
  471.     in Kernighan & Ritchie: right-justification of fields is
  472.     now the default instead of left-justification (you can GET
  473.     left-justification by using a dash in the conversion, as
  474.     specified in the book); the "%s" conversion can take a precision
  475.     now as well as a field width; the "e" and "f" conversions, for
  476.     floating point numbers, are supported in a special version of
  477.     "sprintf" given in source form in the FLOAT.C file. If you do
  478.     a lot of number crunching and wish to have that version be the
  479.     default (it eats up a K or two more than this version), just
  480.     replace this version of sprintf in DEFF.CRL with the one in FLOAT.C,
  481.     using the CLIB program, or else be stuck with always typing in
  482.     "float" on the clink command line...
  483. */
  484.  
  485.  
  486. sprintf(line,format)
  487. char *line, *format;
  488. {
  489.     char _uspr(), c, base, *sptr;
  490.     char wbuf[80], *wptr, pf, ljflag;
  491.     int width, precision,  *args;
  492.     char lpadchr;    /* HRM */
  493.  
  494.     args = (RAM + 0x3fb);
  495.     while (c = *format++)
  496.       if (c == '%') {
  497.         wptr = wbuf;
  498.         precision = 6;
  499.         ljflag = pf = 0;
  500.  
  501.         if (*format == '-') {
  502.             format++;
  503.             ljflag++;
  504.          }
  505.  
  506.         if ( !(width = _gv2(&format))) width++;
  507.  
  508.         if ((c = *format++) == '.') {
  509.             precision = _gv2(&format);
  510.             pf++;
  511.             c = *format++;
  512.          }
  513.  
  514.         lpadchr = '0';/* HRM pad char for non-decimal numeric fields */
  515.         switch(toupper(c)) {
  516.  
  517.         case 'D':    lpadchr = ' ';
  518.                 if (*args < 0) {
  519.                 *wptr++ = '-';
  520.                 *args = -*args;
  521.                 width--;
  522.                 }
  523.  
  524.         case 'U':  base = 10; goto val;
  525.  
  526.         case 'B':  base = 2;  goto val;    /* HRM */
  527.  
  528.         case 'X':  base = 16; goto val;
  529.  
  530.         case 'O':  base = 8;
  531.  
  532.              val:  width -= _uspr(&wptr,*args++,base);
  533.                goto pad;
  534.  
  535.         case 'C':  lpadchr = ' ';    /* HRM */
  536.                *wptr++ = *args++;
  537.                width--;
  538.                goto pad;
  539.  
  540.         case 'S': lpadchr = ' ';    /* HRM */
  541.               if (!pf) precision = 200;
  542.                sptr = *args++;
  543.                while (*sptr && precision) {
  544.                 *wptr++ = *sptr++;
  545.                 precision--;
  546.                 width--;
  547.                 }
  548.  
  549.              pad:  *wptr = '\0';
  550.              pad2: wptr = wbuf;
  551.                if (!ljflag)
  552.                 while (width-- > 0)
  553.                     *line++ = lpadchr;    /* HRM mod */
  554.  
  555.                while (*line = *wptr++)
  556.                 line++;
  557.  
  558.                if (ljflag)
  559.                 while (width-- > 0)
  560.                     *line++ = ' ';
  561.                break;
  562.  
  563.          default:  *line++ = c;
  564.  
  565.          }
  566.       }
  567.       else *line++ = c;
  568.  
  569.     *line = '\0';
  570. }
  571.  
  572. /*
  573.     Internal routine used by "sprintf" to perform ascii-
  574.     to-decimal conversion and update an associated pointer:
  575. */
  576.  
  577. int _gv2(sptr)
  578. char **sptr;
  579. {
  580.     int n;
  581.     n = 0;
  582.     while (isdigit(**sptr)) n = 10 * n + *(*sptr)++ - '0';
  583.     return n;
  584. }
  585.  
  586.  
  587. /*
  588.     Internal functio